#pragma once

#include <vector>

namespace jianzhi_014
{

class Solution
{
public:
    int cuttingRope(int n)
    {
        std::vector<int> max_product(n + 1, 0);
        max_product.at(1) = 1;
        max_product.at(2) = 1;
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j <= i / 2; ++j) {
                auto prod = j * std::max(i - j, max_product.at(i - j));
                max_product.at(i) = std::max(max_product.at(i), prod);
            }
        }
        return max_product.at(n);
    }
};

}  /* namespace jianzhi_014 */
